package recursive;

import org.junit.Test;

public class Queen8 {
    //用于解决八皇后问题
    int max=8;
    int[] array=new int[max];//该数组用于装八皇后所在的列数,数组下标即为皇后所在的行数
    static int count=0;
    @Test
    public void test(){
        for (int i = 0; i < array.length; i++) {
            array[i]=-1;
        }
        check(0);
        System.out.println("共有"+count+"种摆法");
    }
    public boolean judege(int n){
        //判断当前皇后n是否与之前n-1位皇后冲突
           //冲突:第n个皇后不能和前n-1个皇后在同一行,同一列,同对角线
        for (int i=0;i<n;i++){
            if(array[i]==array[n] || Math.abs(array[n]-array[i])==Math.abs(n-i)){
                //两个皇后在同一列
                return false;
                //在同一对角线
                   //array[n],array[i]表示所对应的皇后n和皇后i所在的列,比如分别在3,1;
                    // n,i表示n,i皇后所在的行,比如有有1(i),1(array[i])和3(n),3(aray[n])
                    // 就有取绝对值:array[n]-i==array[i]-n;
            }
        }
        //行不用判断
        return true;
    }
    public void check(int n){
        //该方法用于放置第n个皇后
            //如果皇后放置满八个则退出返回
//        System.out.println("当前皇后:"+n);
        //show(array);
        if(n==max){
            count++;
            printQueen(array);
            return;
        }//未满八个就需要继续放皇后,放皇后时必须使得当前放置的皇后不能与之前放置的皇后冲突
        for (int i=0;i<max;i++){
            array[n]=i;
            if(judege(n)){
                check(n+1);
            }
        }


    }
    public void printQueen(int[] array ){
        //该方法用于输出八皇后队列(array)
        System.out.println("--------八皇后队列-----------");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+"  ");
        }
        System.out.println("");
        System.out.println("--------------------------------");
        System.out.println();
    }
    public void show(int[] array){
        //该方法用于展示当前棋盘现状,用于辅助理解所用
        //皇后所在位置用数字1标识
        int[][] chess = new int[8][8];
        for (int i=0;i<8;i++ ){
           if (array[i]>=0)
            chess[i][array[i]]=1;
        }
        System.out.println("----------当前棋盘开始---------------");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                System.out.print(chess[i][j]+" ");
            }
            System.out.println("");
        }
        System.out.println("---------------当前棋盘结束------------");
        System.out.println("");
    }
}
